package vip.zhenzicheng.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/generate-parentheses/">括号生成[中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-12-26 14:50
 */
public class GenerateParentheses_22 {

  public List<String> generateParenthesis(int n) {
    List<String> ans = new ArrayList<>();
    backtrack(ans, new StringBuilder(), 0, 0, n);
    return ans;
  }

  // 回溯算法
  public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
    if (cur.length() == max * 2) {
      ans.add(cur.toString());
      return;
    }
    if (open < max) {
      cur.append("(");
      backtrack(ans, cur, open + 1, close, max);
      cur.deleteCharAt(cur.length() - 1);
    }
    if (close < open) {
      cur.append(")");
      backtrack(ans, cur, open, close + 1, max);
      cur.deleteCharAt(cur.length() - 1);
    }
  }
}
